//
// Created by Dell on 2021/12/8.
//

#include <iostream>

using namespace std;

struct node{
    int val,height;
    node *left,*right;
};

node *newNode(int v){
    node * Node = new node;
    Node ->val = v;
    Node ->height = 1;
    Node->left = Node->right = NULL;
    return Node;
}
int getHeight(node *x){
    if(x == NULL) return 0;
    return x->height;
}

int getBalanceFactor(node * x){
    return getHeight(x->left) - getHeight(x -> right);
}

void updateHeight(node *x){
    x ->height = max(getHeight(x->left), getHeight(x->right))+1;
}

void search(node *x,int val){
    if(x == nullptr){
        printf("fail");
        return ;
    }
    if(val == x->val){
        printf("Yes");
    }else if(val < x->val){
        search(x->left,val);
    }else{
        search(x->right,val);
    }
    return;
}



void L(node * &x){
    node * tem = x->right;
    x->right = tem->left;
    tem->left = x;
    updateHeight(x);
    updateHeight(tem);
    x = tem;
    return;
}

void R(node *&x){
    node *tem = x->left;
    x->left = tem->right;
    tem->right = x;
    updateHeight(x);
    updateHeight(tem);
    x = tem;
}

void insert(node* & x,int v){
    if (x == nullptr){
        x = newNode(v);
        return;
    }
    if (v<x->val){
        insert(x->left,v);
        updateHeight(x);
        if (getBalanceFactor(x) == 2){
            if(getBalanceFactor(x->left) ==1){
                R(x);
            }else if (getBalanceFactor(x->left) == -1){
                L(x->left);
                R(x);
            }
        }
    }else{
        insert(x->right,v);
        updateHeight(x);
        if(getBalanceFactor(x) == -2){
            if(getBalanceFactor(x->right) == -1){
                L(x);
            }else if (getBalanceFactor(x->right) == 1){
                R(x->right);
                L(x);
            }
        }
    }
}

node *Build(int data[],int n){
    node *root = nullptr;
    for(int i = 0;i<n;++i){
        insert(root,data[i]);
    }
    return root;
}

int main(){
    int data[7] = {88,70,61,96,120,90,65};
    node * root = Build(data,7);
    printf("%d\n",root->val);
    return 0;
}